#pragma once
#include <iostream>
#include <assert.h>
#include <stdbool.h>

//class stack
//{
//public:
//	stack(int n = 4)
//	{
//		_arr = (int*)malloc(sizeof(int) * n);
//		assert(_arr);
//		_top = 0;
//		_capacity = n;
//	}
//
//	~stack()
//	{
//		free(_arr);
//		_arr = nullptr;
//		_top = 0;
//		_capacity = 0;
//	}
//
//	void Push(int x)
//	{
//		if (_top == _capacity)
//		{
//			int newcapacity = 2 * _capacity;
//			int* tmp = (int*)realloc(_arr, sizeof(int) * newcapacity);
//			assert(tmp);
//			_arr = tmp;
//			_capacity = newcapacity;
//		}
//		_arr[_top++] = x;
//	}
//
//	void Pop()
//	{
//		_top--;
//	}
//
//	int Top()
//	{
//		return _arr[_top-1];
//	}
//
//	bool Empty()
//	{
//		return _top == 0;
//	}
//
//	void print()
//	{
//		for (int i = 0; i < _top; i++)
//		{
//			std::cout << _arr[i] << "->";
//		}
//	}
//
//
//private:
//	int* _arr;
//	int _top;
//	int _capacity;
//};

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;
	int capacity;
	int top;
}ST;

void STInit(ST* ps);

void STPush(ST* ps, STDataType x);
void STPop(ST* ps);

STDataType STTop(ST* ps);

bool BoolEmpty(ST* ps);

void STDestroy(ST* ps);


void SelectSort(int* arr, int n);
void ShellSort(int* arr, int n);

void HeapSort(int* arr,int n);

void QuickSort3(int* arr,int left, int right);
void QuickSort2(int* arr, int left, int right);
void QuickSort1(int* arr, int left, int right);
void QuickSort(int* arr, int left, int right);


void print(int* arr,int n );